In International standards for video coding such as MPEG and ITU-T H.26×, Huffman coding has been used for entropy coding. Huffman coding provides an optimum coding performance when individual information symbols are to be represented as individual codewords. Optimum performance is not, however, guaranteed when a signal such as a video signal exhibits localized variation so that the probability of appearance of information symbols varies.
Arithmetic coding is proposed as a method that adapts dynamically to the probability of appearance of individual information symbols and is capable of representing a plurality of symbols as a single codeword.
The concept behind arithmetic coding will be outlined by referring to Mark Nelson, “Arithmetic Coding+Statistical Modeling=Data Compression Part 1—Arithmetic Coding”, Dr. Dobb's Journal, February 1991. It is assumed that an information source generates information symbols comprising alphabets and a message “BILL GATES” is arithmetically coded.
The probability of appearance of individual characters is defined as shown in FIG. 1. As indicated in a column “RANGE” of FIG. 1, portions of a probability line defined by a segment [0, 1) are uniquely established for respective characters.
Subsequently, the characters are subject to a coding process. First, the letter “B” is coded. This is done in the form of identifying a range [0.2, 0.3) on the probability line for that character. Therefore, the letter “B” corresponds to a set of High value and a Low value in the range [0.2, 0.3).
To code “I” subsequently, the range [0.2, 0.3) identified in the process of coding “B” is regarded as a new segment [0, 1) so that a sub-segment [0.5, 0.6) is identified therein. The process of arithmetic coding is a process of successively bounding rages on the probability line.
Repeating the process for the characters, the result of arithmetic coding of “BILL GATES” is represented as a Low value “0.2572167752” of a segment after the coding of the letter “S” is completed.
A decoding process is an inverse of the coding process.
First, the coding result 0.2572167752 is examined to determine a range on the probability line in which the result lies and determine a character assigned to the range. In this case, we restore “B”.
Thereafter, the Low value for “B” is subtracted from the result and the resultant value is divided by the magnitude of the range of “B”, producing “0.572167752”. This enables us to restore “I” corresponding to the segment [0.5, 0.6). The process is repeated until “BILL GATES” is restored by decoding.
By performing an arithmetic coding as described above, a message of extreme length could be mapped onto a single codeword. In actual implementation, it is impossible to operate with infinite decimal precision. Moreover, multiplication and division are necessary for coding and decoding so that heavy computational load is imposed. These problems are addressed by floating-point decimal computation using, for codeword representation, registers of an integer type. The Low value is approximated by a power of 2 so that multiplication and division are replaced by shift operations. Ideally, arithmetic coding according to the above-described process enables entropy coding adapted to the probability of occurrence of information symbols. More specifically, when the probability of occurrence varies dynamically, the coding efficiency higher than that of Huffman coding is available by tracing the variation and updating the table of FIG. 1 appropriately.
Since the digital signal arithmetic coding method and digital arithmetic decoding method according to the related art are configured as described above, each video frame is divided into segments for transmission in units that allows resynchronization (for example, MPEG-2 slice structure) in order to minimize degradation occurring in an entropy-coded video signal due to transmission errors.
Huffman coding maps individual coding symbols into codewords of an integer bit length so that transmission unit is immediately defined as a group of codewords. In arithmetic coding, however, a special code for explicitly suspending a coding process is required. In addition, for resumption of coding, the process of learning the probability of occurrence of earlier symbols should be reset so as to output bits for establishing a code. As a result, the coding efficiency may suffer prior to and subsequent to the suspension. Another problem to be addressed is that, when an arithmetic coding process is not reset while coding a video frame and the frame has to be divided into small units such as packet data for transmission, decoding of a packet cannot take place without the immediately preceding packet data so that significant adverse effects on video quality result when a transmission error or a packet loss due to a delay occurs.
The present invention addresses these problems and has an objective of providing a digital signal coding apparatus and a digital signal coding method capable of ensuring a high degree of error resiliency and improving a coding efficiency of arithmetic coding.
The present invention has a further objective of providing a digital signal decoding apparatus and a digital signal decoding method capable of proper decoding in a situation where the coding apparatus continues coding across bounds of transmission units, by inheriting, instead of resetting, the arithmetic coding status for earlier transmission units or the symbol probability learning status.